import java.util.Arrays;
import java.util.Iterator;
import java.util.Map;

public class PriQue {
    public static void main(String[] args) {

    }

    //无序数组的优先级队列
    class PriorityQueue1<E extends Priority> implements Queue<E>, Iterable<E> {
        Priority[] arr;
        int size;

        public PriorityQueue1(int capacity) {
            this.arr = new Priority[capacity];
        }


        @Override
        public boolean offer(E value) {
            if (isFull()) {
                return false;
            }
            arr[size] = value;
            size++;
            return true;
        }

        @Override
        public E poll() {
            if (isEmpty()) {
                return null;
            }
            E e = (E) arr[findMaxIndex()];
            remove(findMaxIndex());
            return e;
        }

        private void remove(int index) {
            if (index < size - 1) {
                System.arraycopy(arr, index + 1, arr, index, size - 1 - index);
            }
            size--;
            arr[size] = null;
        }

        //寻找最大索引
        private int findMaxIndex() {
            int max = 0;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i].getPriority() > arr[max].getPriority()) {
                    max = i;
                }
            }
            return max;
        }

        @Override
        public E peek() {
            if (isEmpty()) {
                return null;
            }
            int max = findMaxIndex();
            return (E) arr[max];
        }

        @Override
        public boolean isEmpty() {
            return size == 0;
        }

        @Override
        public boolean isFull() {
            return size == arr.length;
        }

        @Override
        public Iterator<E> iterator() {
            return new Iterator<E>() {
                int i = 0;

                @Override
                public boolean hasNext() {
                    return i != arr.length;
                }

                @Override
                public E next() {
                    E e = (E) arr[i];
                    i++;
                    return e;
                }
            };
        }
    }
}

//有序数组实现优先级队列
class PriorityQueue2<E extends Priority> implements Queue<E>{
    Priority[] array;
    int size;

    public PriorityQueue2(int capacity) {
        this.array = new Priority[capacity];
    }


    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        insert(value);
        return true;
    }

    private void insert(E e){
        int i = size-1;
        while (i>=0 && array[i].getPriority() > e.getPriority()){
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = e;
    }

    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        E e = (E)array[size-1];
        size--;
        array[size] = null;
        return e;
    }

    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        return (E) array[size-1];
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public boolean isFull() {
        return size==array.length;
    }
}


//基于堆实现优先级队列
class PriorityQueue3<E extends Priority> implements Queue<E>{
    Priority[] array;
    int size;

    public PriorityQueue3(int capacity) {
        this.array = new Priority[capacity];
    }



    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        int child = size;
        size++;
        int parent = (child-1) / 2;
        while (child>0 && value.getPriority()>array[parent].getPriority()){
            array[child] = array[parent];
            child = parent;
            parent = (child-1) / 2;
        }
        return true;
    }


    private void swap(int i,int j){
        Priority t =  array[i];
        array[i] = array[j];
        array[j] = t;
    }
    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        swap(0,size-1);
        size--;
        Priority p = array[size];
        array[size] = null;

        //下潜寻找
        down(0);
        return (E) p;
    }

    private void down(int parent){
        int left = 2 * parent + 1;
        int right = left + 1;
        int max = parent;  //默认最大为父亲
        if (left<size && array[left].getPriority()>array[max].getPriority()){
            max = left;
        }
        if (right<size && array[right].getPriority()>array[max].getPriority()){
            max = right;
        }
        if (max != parent){
            swap(max,parent);
            down(max);
        }
    }

    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public boolean isFull() {
        return size==array.length;
    }
}



